This invention relates to methodology for optimization of manufacturing resource planning (MRP), including resource allocation and production planning, by linear programming and, more particularly, to optimization of MRP for a multiple level assembly process by use of an optimal resource allocation procedure to determine shipment and production schedules, these schedules to be included in data of the MRP process.
A need for resource allocation decisions arises in a broad range of technological and industrial areas such as the assignment of transmission facilities in telephone transmission systems, the control of the product mix of a factory, the deployment of industrial equipment, and inventory control, by way of example. Resource allocation in this context means, in general, the deployment of specific technological or industrial resource for the production of particular technological or industrial results.
Resource allocation decisions are typically subject to constraints such as limitations in availability of materials, equipment, time, cost, and other parameters affecting the outcome of a technological process, as well as the utility of a particular resource in a particular application. As an example of particular interest herein, there is need to optimize the MRP for production of products, such as semiconductor devices, particularly in a situation wherein plural intermediate products must be formed first during various time frames for subsequent combination to provide the end product. Each particular allocation of resources can be associated with a specific result such as the cost or number of products produced. Ideally, resources should be allocated so as to satisfy all of the constraints and, simultaneously, to maximize a resulting benefit, such as by minimizing the costs or by maximizing the number of devices outputted by a manufacturing process.
One method of representing such allocation decision problems is known as a linear programming model. Such a model consists of a number of linear relationships, set forth in matrix format, and representing quantitatively the relationships among allocations, constraints and results of an industrial or other technological process. In the linear relationships, there is provided the sum of constant coefficients multiplied by unknown allocation values. While many resource allocation problems are not represented by such linear relationships, but involve higher powers or other nonlinear expression of equation variables, the optimization of MRP processes has been treated by a linear model. Such modeling by linear programming (LP) is accomplished in multidimensional space with multidimensional vectors providing a multidimensional figure, or polytope, wherein each facet on a surface thereof is bounded by equations defining relationships among allocated inputs to the industrial process. An optimum solution to the LP problem has been obtained by use of the Simplex algorithm developed by George Dantzig in 1947, by way of example, or by the more recent Karmarkar algorithm, as disclosed in U.S. Pat. No. 4,924,386 of Freedman et al.
A problem arises in that present systems and methodology for processing MRP procedures are limited to a prediction of the amount of products, such as semiconductor devices, to be outputted from a manufacturing facility for a given set of input parameters, such as amounts of various raw materials, available equipments and available time, for a succession of manufacturing steps. The presently available systems and methodology are unable to perform an optimization process for MRP, based on a linear objective function such as minimization of cost or maximization of the number of outputted devices. Thus, at the present time, a manufacturer can guess at a possible set of input parameters which might produce a near optimum result, and apply this to an MRP system which would predict the outcome. But there are no assurances that the predicted outcome would be near optimum.
The need for a method of optimizing a manufacturing process can be appreciated by considering the large worldwide market for manufacturing information systems (MIS) which contain data and data-processing methods that aid manufacturing managers in production planning and execution. For example, an MIS contains demand data, supply data, cost data, and bill-of-material data, and includes MRP software, capacity requirements planning (CRP) software, order-tracking software, and financial-reporting software. The market for just MRP is in the billions of dollars. MIS software is available for computers ranging from mainframes to desktops.
Presently available MIS is directed primarily to data management systems. Most important manufacturing decisions (for example, what to make, how much to make, when and where to make it) are ultimately made by humans rather than by an MIS. Typically, a manufacturer uses intuition and experience together with knowledge about manufacturing capacity and market demand to determine an initial production plan. Then the manager would run MRP and/or CRP to produce reports describing inconsistencies between a production plan and availability of a resource. This would be followed, possibly, by a revision of the production plan with a rerun of the MRP and the CRP. This is time consuming, and the reports are difficult to interpret for purposes of revising a production plan so as to alleviate a shortage of a particular material employed in the production process. An attempt to run an infeasible production plan can result in missed customer shipments, excess raw material inventory, long cycle times, production bottlenecks, poorly utilized capacity, and idle workers. Even when the production plan is feasible, the manufacturer must deal with the lengthy process of manually revising the production plan until receipt of a report from MRP and CRP indicating no shortages. The process can result in poor resource allocation decisions, such as the allocation of scarce resources to low profit products.
The limitations of presently available MRP result in a common manufacturing problem which is a shortage of raw material or subassemblies. For example, in the situation wherein a manufacturer has more orders than can be filled, the manufacturer would like to fill the orders in a manner which would maximize the profit, or which would minimize the inventory, or would meet some other goal.